
tr = [None,{"w":2,"v":3},
      {"w":3,"v":4},
      {"w":4,"v":8},
      {"w":5,"v":8},
      {"w":9,"v":10}]

able=20

process = [[0]*(able+1) for _ in range(len(tr))]
path = [[""]*(able+1) for _ in range(len(tr))] 

for item in range(1,len(tr)):
    for weight in range(1,able+1):
        if weight == 0 or item ==0:
            process[item][weight]=0
        elif tr[item]['w']>weight:
            path[item][weight]=path[item-1][weight]
            process[item][weight]=process[item-1][weight]
        else:
            VN=process[item-1][weight]
            VY=process[item-1][weight-tr[item]['w']]+tr[item]['v']
            if VN>VY:
                path[item][weight]=path[item-1][weight]
                process[item][weight]=VN
            else:
                path[item][weight]=path[item-1][weight-tr[item]['w']]+f"_{item}"
                process[item][weight]=VY


print(f"价值最高：{process[-1][-1]}")
max_items=map(int,path[-1][-1].split("_")[1:])
print("采用如下选择：")
print(f"item\tweight\tvalue")
for i in max_items:
    print(f"{i}\t{tr[i]['w']}\t{tr[i]['v']}")